package algorithms.leecode;

import java.util.List;
import java.util.Set;

public class Au44 {
    public static void main(String[] args) {
 //       "abcabczzzde"
 //       "*abc???de*"
        String s ="abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb";
        String p ="**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb";
//        String s = "c";
//        String p = "*?*";
//        String s = "abcabczzzde";
//        String p = "*abc???de*";
        System.err.println(isMatch(s,p));
    }
    public static boolean isMatch(String s, String p) {
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        boolean[] con = new boolean[10000];
        boolean res = match(sArr, pArr, 0, 0,con);

        return res;
    }

    public static boolean match(char[] sArr, char[] pArr, int sIndex, int pIndex, boolean[] con) {
        if (con[pIndex]) {
            return false;
        }
        // 连续*问题
       if (pIndex < pArr.length - 1) {
           if (pArr[pIndex] == '*') {
               while (pArr[pIndex + 1] == '*') {
                   pIndex++;
                   if (pIndex == pArr.length - 1) {
                       break;
                   }
               }
           }

       }
       if (pIndex == pArr.length - 1) {
           if (pArr[pIndex] == '*') {
               return true;
           }
       }
        if (sIndex == sArr.length && pIndex == pArr.length) {
            return true;
        } else if ((sIndex == sArr.length && pIndex != pArr.length)
                || (sIndex != sArr.length && pIndex == pArr.length)) {

            return false;
        }
        if ((sArr[sIndex] == pArr[pIndex])
                || pArr[pIndex] == '?') {
            sIndex++;
            pIndex++;
            return match(sArr, pArr, sIndex, pIndex,con);
        } else if (pArr[pIndex] == '*') {
            while (pArr[pIndex + 1]  == '*') {
                pIndex++;
            }
            if (pIndex == pArr.length - 1) {
                return true;
            } else if (pArr[pIndex + 1] != sArr[sIndex] && pArr[pIndex + 1] != '?') {
                sIndex++;
                return match(sArr, pArr, sIndex, pIndex,con);
                // 如果当前和下一个匹配
            } else if (pArr[pIndex + 1] == sArr[sIndex] || pArr[pIndex + 1] == '?') {
                int tmpSIndex = sIndex;
                int tmpPIndex = pIndex;
                // 跳过'*'让其匹配
                tmpPIndex++;
                if (match(sArr, pArr, tmpSIndex, tmpPIndex,con)) {
                    return true;
                }
                int tmpIndex1 = sIndex;
                int tmpPIndex1 = pIndex;
                //        跳过当前尝试后续;
                tmpIndex1++;
                //            tmpPIndex1++;
                if (match(sArr, pArr, tmpIndex1, tmpPIndex1,con)) {
                    return true;
                }
                con[pIndex] = true;

            }
        } else {

            return false;
        }
        return false;
    }

}
